A CAM is a memory device which allows a processor within a computer, to perform a parallel search through the CAM's stored data in order to retrieve the address of any matching stored data if such data is found. The search and stored data can be either binary (comprising logic “1” or “0” state) or ternary (logic “1”, “0” or “don't care” states) data.
A CAM is usually subdivided in banks of CAM cell arrays. A CAM array comprises a plurality of CAM cells arranged in rows and columns with row of the cell being connected to an associated match line and cells being connected to associated search lines. The cells are also coupled to wordlines and bitlines for retrieving information out of and for storing information in the CAM.
During a search operation, search data often referred to as a search key of a particular width is placed on the search lines. The search key on the search data lines is compared with stored data in all CAM cell locations simultaneously and a match (also referred to as a “hit”) or mismatch result (also referred to as a “miss”) is provided to match lines coupled to each CAM cell. If the search key matches the information stored in a particular row in the CAM, the associated match line will indicate a hit or match condition. If the search key and the stored data are different, the associated match line will indicate a miss or mismatch condition. All match line outputs are processed by a multiple match resolver (MMR) and priority encoder (PE) block that will provide as an output signal the highest priority match address where the match information is located.
Conventional CAM's are mode configurable to perform search operations on data words having specific word widths for example, 144 bit or 288 bit search modes. Typically in such CAM's, a configuration register stores the operating mode of the device and fields within the register specify the word width. Data will be written into the CAM according to the word width setting in the mode register and search instructions issued to the CAM will therefore search the stored data based on the word width specified in the configuration register. In order to change the word width the mode register must first be updated and then the new search is performed. Thus, variable word width searching “on-the-fly” is not supportable by such conventional CAM's. Thus, although pre-set word-width CAM's do exist, there is still a need for a CAM that supports arbitrary word width searches and which is capable of switching between one or more types of searching on-the-fly.
Some conventional approaches have been proposed for searching words which are wider than default word widths stored in a CAM, for example in U.S. Pat. No. 6,252,789 to Pereira et al. Such approaches however require extra width expansion circuitry associated with each CAM row for handling situations when search data words that are wider than the default stored word width. Furthermore, such width expansion circuitry are interconnected and a match result is not provided to a priority encoder until the last word in a multiword data chain has been compared to the contents of the data stored in the CAM. This approach therefore is only effective in exact match multiple word searches.
Thus, there is still a need for a CAM that is capable of performing variable word width searching with search data widths that can be changed on-the-fly, and while storage of data words makes efficient use of the CAM.